This invention is related to the field of design automation of VLSI chips, and more particularly, to a method of reducing the complexity of a floorplanner by solving the mix of large blocks and cell placement while preserving the accuracy of the floorplanner.
With the increasing size and complexity of VLSI (Very Large Scale Integrated) circuit designs, the physical design task of floorplanning is gaining more relevance in today""s design methodologies. These designs consist of a mix of large cells (the height of the object spanning over several circuit rows) and smaller ones. A VLSI design is represented by a netlist consisting of a set of blocks, large and small, interconnected by nets. (Nets can be viewed as wires or interconnections that link the various blocks in the design). A block may be a hard block, whose area and shape are already fixed, or a soft block consisting of smaller cells, and whose area and shape are flexible. Examples of large hard blocks are register arrays, memories, and the like. The blocks may also be small leaf level gates within the design, commonly referred to as leaf level cells. Floorplanning determines the best placement of the large blocks. Blocks that are to be placed on the layout by the floorplanner are termed xe2x80x9cfloorplan objects of interestxe2x80x9d or simply large blocks
A typical approach to determine the best location of large blocks in a netlist consisting of a mixture of large blocks and small leaf level cells is to first group the smaller leaf level cells into large blocks. By way of example, the original netlist (consisting of large blocks and small leaf cells) is transformed, by performing some sort of clustering/partitioning, into a netlist consisting of large blocks.
Given a flat VLSI netlist, the step of creating flexible blocks from small leaf cells in the design amounts to creating a level of hierarchy therein. This step is achieved by grouping a set of cells into a separate flexible block. Grouping introduces extra floorplan objects of interest into the design. This type of explicit hierarchy creation has its own drawbacks since it introduces extra steps in the design process, potentially increasing the turnaround time (TAT) of the design.
When a transformed netlist is made of large blocks or floorplan objects of interest, the task of determining their locations on the layout can be done manually based on the design""s architectural constraints or automatically. In the latter case, algorithmic techniques for global optimization are used, such as simulated annealing driven by a cost function that minimizes objectives like the total wire length between the large blocks. The term simulated annealing is derived from an analogous physical process of heating and then slowly cooling a substance to obtain a strong crystalline structure. In simulated annealing, the minimum cost function corresponds to the ground state of the substance. The simulated annealing process lowers the temperature in slow stages until the system xe2x80x9cfreezesxe2x80x9d, after which no further changes occur. To apply simulated annealing, the system is initialized with a particular configuration. A new configuration is constructed by imposing a random displacement. If the energy of the new state is lower than the previous one, the change is accepted unconditionally and the system is updated. If the energy is greater, the new configuration is accepted probabilistically. More details regarding this technique are found in the article xe2x80x9cOptimization by Simulated Annealingxe2x80x9d by Kirkpatrick, Gellatt and Vecchi, published in the 1983 edition of Science. Subsequent placement of the leaf level cells is sensitive to the quality of the floorplan (location of large blocks in the design). Thus, achieving a good initial floorplan is critical for obtaining high quality final placement solutions.
Conventional floorplanning uses a representation wherein intermediate leaf levels cells are clustered to form the nodes of the netlist amounting to the previously stated creation of a hierarchical level. However, these do not describe a methodology wherein the abstracted cells are represented as abstract interconnections with constraint annotations (that helps to preserve the potential signal path behavior of the design), and which efficiently drives the optimization floorplanning algorithm with a path based abstract interconnection representation. (Abstract interconnections are referred as such because they do not exist in the given netlist, but are introduced in the present invention in order to account for intermediate leaf cells and related nets that were removed from the original netlist. Abstract interconnections will also be referred to hereinafter as abstract hyper-edges or abstract nets. A hyper-edge is a known term used in graph theory to indicate a connection between multiple nodes in a graph).
Simulated annealing has been used in the art as an effective floorplanning algorithm because of its ability to handle various constraints, such as block shapes, I/O constraints, etc. This technique belongs to a class of algorithms called xe2x80x9chill-climbing algorithmsxe2x80x9d that have the ability of finding near-optimal solutions to the problem on hand. However, the algorithm requires vast amounts of computational resources and is inherently slow. The algorithm is an iterative improvement algorithm. In each iteration, several solutions are generated by perturbing the initial solution. Then, the quality of the solutions is evaluated, the measure of quality forming the basis for their acceptance or rejection. A cost function is finally used to compute this measurement.
Some reasons for the inherent slowness of the annealer arise from the near-exhaustive nature of the solution space being contemplated, and from the time taken for evaluating the quality of the solution. The floorplanner that is used in the abstraction based flow is based on simulated annealing. In this context, novel techniques to reduce the complexity of an annealing based floorplanner working within a path based abstraction flow will also be described in the present invention hereinafter.
Referring to FIG. 1, the outline of a conventional physical design methodology is shown. The chip physical design step starts with floorplanning. The task of floor-planning results in associating coordinate locations to floorplan objects of interest on the two-dimensional region representing the chip layout.
Upon completion of the floorplanned design, the next step of placement results in associating specific coordinate locations for all remaining design objects in the netlist (other than the floorplan objects of interest). The objective is to arrive at valid locations for the floorplan objects of interest, in order that subsequent steps of the chip physical design may be successfully completed. Present techniques are known to be ineffective in optimizing a floorplan design.
Thus, it is an object of the invention to provide a method to optimize the floorplan of a VLSI chip using a path based hyper-edge representation.
It is another object to provide a framework consisting of a path oriented abstract representation of detailed VLSI design netlists alongside with mechanisms for generating them efficiently, and appropriate techniques for interfacing with, and for driving optimization based floorplanning algorithms
It is still another object to improve the efficiency of the floorplanner by reducing the complexity of an annealing based floorplanner working within a path based abstraction flow.
It is a further object to execute the abstraction phase by abstracting the leaf level logic (to reduce the solution space of the floorplanner) and reintroduce them in the form of floorplan constraints (to account for the presence of the leaf level logic while determining the location of large blocks).
It is yet another object to achieve by way of abstraction a significant improvement in the performance of a simulated annealing based floorplanner.
In a first aspect of the invention, there is described an abstraction based methodology to floorplanning. The abstraction method employs a hybrid, controlled path enumeration approach to generate a model that is used by the floorplanner. The abstraction methodology retains all the floorplan objects of the model that are of interest, while the abstracted cells in the input netlist are represented as directed hyper-edges with constraint annotations. The representation of abstracted cells as attributed hyper-edges, instead of complex (i.e., hierarchical) blocks, helps to preserve the signal path oriented behavior of the design, communicating it to the floorplanner. The physical design task of floorplanning is typically unaware of the structure of design netlist that is being floorplanned. The path based abstraction technique of the present invention also provides structural properties (path information between specific floorplan objects of interest) of the netlist to the floorplanner. This is done without any significant sacrifice in the quality of the resulting solutions.
The concept of path based netlist abstraction and net bundling are an essential aspect of the abstraction process. Netlist abstraction (described above) prunes the solution space by identifying objects of interest from the netlist and determining the connectivity between them. The net-bundling step significantly reduces the time taken for evaluating the floorplan solution quality by efficiently handling the connectivity information between objects of interest.
In another aspect of the invention, there is provided a method for optimizing a floorplanner for a design netlist representation of an integrated circuit (IC) chip that includes the steps of: a) generating an abstract netlist; b) bundling the abstract netlist resulting in a reduced abstract netlist; c) generating constraints for the floorplanner; and d) modeling the constraints in the floorplanner to place floorplan objects of interest on the chip layout.